package com.hy.dp;

public class MinCostClimbStairs {


    /**
     *
     * 746. 使用最小花费爬楼梯
     * 力扣题目链接
     *
     * 数组的每个下标作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值 cost[i]（下标从 0 开始）。
     *
     * 每当你爬上一个阶梯你都要花费对应的体力值，一旦支付了相应的体力值，你就可以选择向上爬一个阶梯或者爬两个阶梯。
     *
     * 请你找出达到楼层顶部的最低花费。在开始时，你可以选择从下标为 0 或 1 的元素作为初始阶梯。
     *
     * 示例 1：
     *
     * 输入：cost = [10, 15, 20] 输出：15 解释：最低花费是从 cost[1] 开始，然后走两步即可到阶梯顶，一共花费 15 。
     *
     * 思路
     * 这道题目可以说是昨天动态规划：爬楼梯的花费版本。
     *
     * 注意题目描述：每当你爬上一个阶梯你都要花费对应的体力值，一旦支付了相应的体力值，你就可以选择向上爬一个阶梯或者爬两个阶梯
     *
     * 所以示例1中只花费一个15 就可以到阶梯顶，最后一步可以理解为 不用花费。
     *
     * 读完题大家应该知道指定需要动态规划的，贪心是不可能了。
     * 1. 确定dp数组以及下标的含义
     * 使用动态规划，就要有一个数组来记录状态，本题只需要一个一维数组dp[i]就可以了。
     *
     * dp[i]的定义：到达第i个台阶所花费的最少体力为dp[i]。（注意这里认为是第一步一定是要花费）
     *
     * 对于dp数组的定义，大家一定要清晰！
     * 2.确定递推公式
     * 可以有两个途径得到dp[i]，一个是dp[i-1] 一个是dp[i-2]。
     *
     * 那么究竟是选dp[i-1]还是dp[i-2]呢？
     *
     * 一定是选最小的，所以dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i];
     * 3.dp数组如何初始化
     * dp[0] = cost[0];
     * dp[1] = cost[1];
     * 4.确定遍历顺序
     * 因为是模拟台阶，而且dp[i]又dp[i-1]dp[i-2]推出，所以是从前到后遍历cost数组就可以了。
     *
     * 但是稍稍有点难度的动态规划，其遍历顺序并不容易确定下来。
     * @param cost
     * @return
     */
    public int climbStairs(int [] cost){
        if (cost == null || cost.length == 0){
            return 0;
        }
        if (cost.length == 1){
            return cost[0];
        }
        int [] dp = new int[cost.length + 1];
        // 默认第一步都是不花费体力的
        dp[0] = cost[0];
        dp[1] = cost[1];
        for (int i = 2; i < cost.length; i++) {
            dp[i] = Math.min(dp[i - 1] , dp[i - 2]) + cost[i];
        }
        //最后一步，如果是由倒数第二步爬，则最后一步的体力花费可以不用算
        return Math.min(dp[cost.length - 1],dp[cost.length - 2]);
    }

    public static void main(String[] args) {
        MinCostClimbStairs minCostClimbStairs = new MinCostClimbStairs();
        int[] cost = {10,15,20};
        System.out.println("res: "+minCostClimbStairs.climbStairs(cost));
    }
}
